package com.ys.作业;

/**
 * 描述:
 * 二分查找法,针对有序序列
 *
 * @author CodeYang
 * @version 2020/12/24 9:49
 */
public class 递归得二分查找法 {


    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 5, 9, 12, 65, 128, 200, 300};
        int target = 128;
        System.out.println(binarySearchRecursion(arr, 0, arr.length - 1, target));
        System.out.println(binarySearchWhile(arr, 0, arr.length - 1, target));

    }

    /**
     * 二分查找法:递归实现
     * 递归; 入口在前,出口在后 入口可以有多个,出口也可以有多个
     * 查找规则: 核心公式
     * int mid = left + right / 2
     * 查找规则:
     * (出口之一)
     * 1  arr[mid] == target 返回 arr[mid]
     * 2 arr[mid] < target   证明 查找元素在 中间值 左区域 所以把右区域-1 right = mid -1
     * 3 arr[mid] > target   证明 查找元素在 中将值 右区域 所以把左区域+1 left = left+1
     *
     * @param arr   查找得有序数组
     * @param left  左区域
     * @param right 右区域
     * @return -1 查找失败, 成功返回
     */
    static int binarySearchRecursion(int arr[], int left, int right, int target) {
        if (arr == null) {
            return -1;
        }
        if (left <= right) {
            // 中间值索引
            int mid = (left + right) / 2;
            int midValue = arr[mid];

            if (target == midValue) {
                // 递归头 出口
                return arr[mid];
            } else if (target < midValue) {
                // target < =  midValue 在左半区查找  right = mid-1
                return binarySearchRecursion(arr, left, mid - 1, target);
            } else {
                // target > =  midValue 在左半区查找  left = mid+1
                return binarySearchRecursion(arr, mid + 1, right, target);
            }

        }
        // 执行到此处证明查找失败
        return -1;

    }

    /**
     * 递归调用: 循环实现法:
     *
     * @param arr
     * @param left
     * @param right
     * @param target
     * @return
     */
    static int binarySearchWhile(int arr[], int left, int right, int target) {
        /**
         *  因为 left > right 证明 游标错过,不存在该元素
         */
        while (left <= right) {
            // 中间值索引
            int mid = (left + right) / 2;
            if (target == arr[mid]) {
                return arr[mid];
            } else if (target < arr[mid]) {
                // target < =  midValue 在左半区查找  right = mid-1
                right = mid - 1;
            } else {
                // target > =  midValue 在左半区查找  left = mid+1
                left = mid + 1;
            }
        }
        return -1;
    }


}
